P4450 双亲数

显然,题目求的是:

i=1nj=1m[gcd(i,j)=d]\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d]

i=1ndj=1md[gcd(i,j)=1]\sum_{i=1}^{ \lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}[gcd(i,j)=1]

有一个与莫比乌斯函数有关的性质:dnμ(d)=[n=1]\sum_{d | n}\mu(d)=[n=1]

i=1ndj=1mdkgcd(i,j)μ(k)\sum_{i=1}^{ \lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{k|gcd(i,j)}\mu(k)

kk 往前移,然后是一个非常经典的式子了

k=1min(nd,md)μ(k)nkdmkd\sum_{k=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(k)\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor

用数论分块即可解决。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 1000000;
int a , b , d , k , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			mu[ i ] = -1;
		}
		for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
    for( int i = 1 ; i <= MAXN ; i ++ )
        f[ i ] = f[ i - 1 ] + mu[ i ];
}

long long solve( int n , int m , int k ) {
    int d = min( n , m ); long long Ans = 0;
    for( int l = 1 , r ; l <= d ; l = r + 1 ) {
        r = min( n / ( n / l ) , m / ( m / l ) );
        Ans = Ans + 1ll * ( f[ r ] - f[ l - 1 ] ) * ( n / k / l ) * ( m / k / l );
    }
    return Ans;
}

int main( ) {
    sieve( );
    scanf("%d %d %d",&a,&b,&d);
    printf("%lld",solve( a , b , d ));
    return 0;
}